//给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位
//。 
//
// 返回滑动窗口中的最大值。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
//输出：[3,3,5,5,6,7]
//解释：
//滑动窗口的位置                最大值
//---------------               -----
//[1  3  -1] -3  5  3  6  7       3
// 1 [3  -1  -3] 5  3  6  7       3
// 1  3 [-1  -3  5] 3  6  7       5
// 1  3  -1 [-3  5  3] 6  7       5
// 1  3  -1  -3 [5  3  6] 7       6
// 1  3  -1  -3  5 [3  6  7]      7
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], k = 1
//输出：[1]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,-1], k = 1
//输出：[1,-1]
// 
//
// 示例 4： 
//
// 
//输入：nums = [9,11], k = 2
//输出：[11]
// 
//
// 示例 5： 
//
// 
//输入：nums = [4,-2], k = 2
//输出：[4] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 105 
// -104 <= nums[i] <= 104 
// 1 <= k <= nums.length 
// 
// Related Topics 队列 数组 滑动窗口 单调队列 堆（优先队列） 
// 👍 1316 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class SlidingWindowMaximum {
    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        new SlidingWindowMaximum().new Solution().maxSlidingWindow(nums,3);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 暴力解法：非常拉跨
         */
        public int[] maxSlidingWindow1(int[] nums, int k) {
            int len = nums.length;
            int[] res = new int[len-k+1];
            Arrays.fill(res, Integer.MIN_VALUE);
            for (int i = k-1; i < len; i++) {
                for (int j = i; j >= i-k+1 ; j--) {
                    res[i-k+1] = Math.max(res[i-k+1],nums[j]);
                }
            }
            return res;
        }

        /**
         * 对暴力解法进行了优化，还是超时了
         */
        public int[] maxSlidingWindow2(int[] nums, int k) {
            int len = nums.length;
            if (len == 1 || k == 1) return nums;
            int[] res = new int[len-k+1];
            Arrays.fill(res, Integer.MIN_VALUE);
            for (int l = 0; l < k; l++) {
                res[0] = Math.max(res[0],nums[l]);
            }
            int j = 1;
            for (int i = k; i < len; i++) {
                if (nums[i]>=res[j-1]) res[j] = nums[i];
                else if (res[j-1] != nums[i-k]) res[j] = res[j-1];
                else {
                    for (int l = i; l >= i-k+1 ; l--) {
                        res[j] = Math.max(res[j],nums[l]);
                    }
                }
                j++;
            }
            return res;
        }

        /**
         * 维护一个单调队列（使用双向队列）
         *  队列中存放的是当前窗口可能的最大值，而且队列头部就是当前窗口的最大值
         * 例如 1 2 3 k=3的时候，queue中只会存放3这个元素
         * 例如 1 2 3 2 1 4，k = 3时
         * 第一轮：queue -> 3 返回3
         * 第二轮：queue -> 3,2 返回3
         * 第三轮：queue -> 3,2,1 返回3
         * 第四轮：queue -> 4 返回4（因为4将比自己小的元素都弹出了）
         */
        public int[] maxSlidingWindow(int[] nums, int k) {
            int len = nums.length;
            if (len == 1 || k == 1) return nums;
            int[] res = new int[len-k+1];
            MyQueue queue = new MyQueue();
            for (int i = 0; i < k; i++) queue.push(nums[i]);//对前k个元素先排列一下
            res[0] = queue.front();//赋第一个值
            for (int i = k; i < len ; i++) {
                queue.pop(nums[i-k]);//尝试去掉上这次移动抹去的值
                queue.push(nums[i]);//为队列添加新出现的值
                res[i-k+1] = queue.front();//获取当前窗口最大值
            }
            return res;
        }
        class MyQueue{
            Deque<Integer> deque;
            public MyQueue(){
                deque = new LinkedList<>();
            }

            public void push(int value){
                //移动到新窗口，添加新元素时与队尾进行比较，当前元素大就去掉之前的元素
                while (!deque.isEmpty() && value > deque.peekLast()) deque.pollLast();
                deque.addLast(value);
            }

            public void pop(int value){
                //弹出上一个窗口的剩余值，如果上一个窗口的第一个值恰好最大，必须将其弹出再维护队列
                if (!deque.isEmpty() && deque.peekFirst() == value) deque.pollFirst();
            }

            public int front(){
                //得到当前窗口的最大值，其实就是队列头部的值
                return deque.peekFirst();
            }

        }

        /**
         * 维护一个最大值队列，窗口变化时，最大值队列通过值的比较进行出栈和入栈
         */
        public int[] maxSlidingWindow3(int[] nums, int k) {
            Deque<Integer> deque = new ArrayDeque<>();
            int len = nums.length;
            int[] res = new int[len - k + 1];
            for (int i = 0; i < k; i++){
                // 队列右边小的话入栈，如果当前值大的话一直弹栈
                while (!deque.isEmpty() && deque.peekLast() < nums[i]) deque.pollLast();
                deque.addLast(nums[i]);
            }
            int start = 0, end = k - 1, index = 0;
            while (end < len){
                // 每次进来之后先保存结果
                res[index++] = deque.peekFirst();
                if (index == res.length) break;// 终点判断
                // 根据窗口左端值判断是否需要出栈
                if (nums[start] == deque.peekFirst()) deque.pollFirst();
                // 窗口移动
                start++;
                end++;
                // 根据新加入的值判断是否要更新最大值队列
                while (!deque.isEmpty() && deque.peekLast() < nums[end]) deque.pollLast();
                deque.addLast(nums[end]);
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}





























